package com.yequan.leetcode.greedy.canJump_55;

/**
 * //给定一个非负整数数组，你最初位于数组的第一个位置。
 * //
 * // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * //
 * // 判断你是否能够到达最后一个位置。
 * //
 * // 示例 1:
 * //
 * // 输入: [2,3,1,1,4]
 * //输出: true
 * //解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: [3,2,1,0,4]
 * //输出: false
 * //解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 * //
 * // Related Topics 贪心算法 数组
 *
 * @author : Administrator
 * @date : 2020/4/12
 */
public class CanJump {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        CanJump canJump = new CanJump();
        boolean b = canJump.canJump1(nums);
        System.out.println(b);
    }

    /**
     * 倒着推
     * 要想到达最后的位置,就必须能到达前一个位置
     */
    public boolean canJump1(int[] nums) {
        int targetPos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= targetPos) {
                targetPos = i;
            }
        }
        return targetPos == 0;
    }

    public boolean canJump2(int[] nums) {
        int targetPos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= targetPos) {
                targetPos = i;
            }
        }
        return targetPos == 0;
    }

    public boolean canJump3(int[] nums) {
        int prePos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= prePos) {
                prePos = i;
            }
        }
        return prePos == 0;
    }

    public boolean canJump4(int[] nums) {
        int prePosition = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= prePosition) {
                prePosition = i;
            }
        }
        return prePosition == 0;
    }

    public boolean canJump5(int[] nums) {
        int targetPos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= targetPos) {
                targetPos = i;
            }
        }
        return targetPos == 0;
    }

    public boolean canJump6(int[] nums) {
        int targetPos = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= targetPos) {
                targetPos = i;
            }
        }
        return targetPos == 0;
    }
}
